package cn.corffen.test.algorithm.leetcode.easy;

import java.util.Locale;

/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * <p>
 * 示例:
 * <p>
 * 输入: [-2,1,-3,4,-1,2,1,-5,4],
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 * 进阶:
 * <p>
 * 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Question53 {

    public static void main(String[] args) {
        Question53 solution = new Question53();
        int[] a = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
//        int max = solution.maxSubArray2(a);
//        System.out.println(String.format(Locale.CHINA, "max = %d", max));
        int min = solution.minSubArray(a);
        System.out.println(String.format(Locale.CHINA, "min = %d", min));

        //    数组 -2, 1, -3, 4, -1, 2, 1, -5, 4
        //当前总和 -2, 1, -2, 4, 3, 5,   6,   1, 5
        //  最大值 -2, 1, 1, 4, 4,  5,   6,    6,6
    }

    /**
     * 贪心算法
     * 将数组作为输入,遍历数组,每一步都是最佳方案,遍历完就是全局最优方案.
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < n; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    /**
     * 动态规划
     * 可以把一个大问题拆分成若干个小问题,而这些小问题可以重复利用.
     * 这里遍历数组过程中,如果上一步的值是>0的,那么就将当前值+上一步的值,那么最大值就是当前值
     * 与历史最大值中的较大值
     * 如果上一步的值<0,那么从当前值开始统计即为最大值.
     *
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        int n = nums.length;
        int maxSum = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] > 0) {
                nums[i] += nums[i - 1];
            }
            maxSum = Math.max(maxSum, nums[i]);
        }
        return maxSum;
    }

    public int minSubArray(int[] nums) {
        int n = nums.length;
        int minSum = nums[0];
        int currentSum = nums[0];
        for (int i = 1; i < n; i++) {
            currentSum = Math.min(nums[i], currentSum + nums[i]);
            minSum = Math.min(currentSum, minSum);
        }

        return minSum;
    }

    public int minSubArray2(int[] nums) {
        int n = nums.length;
        int minSum = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] < 0) {
                nums[i] += nums[i - 1];
            }
            minSum = Math.min(nums[i], minSum);
        }

        return minSum;
    }

}
